The present invention relates to a method for rasterizing a page in the operation of a high-speed printing system, and more particularly, to a multiprocessor system and method for banding and rasterizing an output page image in which the speed of a raster image processor is optimized.
The printing industry has undergone significant advances in recent years, to the point that a print engine in a high-speed printing system now has the capability to print over a page per second. Printing technology is now so advanced, that printing capabilities are no longer limited by the print engine speed, but rather by the amount of processing time required to convert a page image from an application program format to a pagemap which can be processed by the print engine. The processing time required to generate a pagemap is a significant problem, since the demand for printing increasingly more complex images continues.
The printing process begins with the development of a page image in an application program such as Adobe Illustrator or Microsoft Word. To transform the page from the workstation display screen to a tangible document form, the application program generates a specification of the page's contents in a page description language or "PDL", such as Postscript by Adobe Systems Inc. The application program generates the specification in the form of a datastream of page description code which contains information regarding each of the objects on the page, the page address for each of the objects, and the format in which the objects appear on the page, such as the applicable font, shading, size and angle. The datastream is transferred from the workstation to a printer, where it is converted into a pagemap, which is a collection of millions of bits which each represent one point or dot on the page, also called a bitmap or raster image.
Traditionally, printing systems have utilized a single processor which interacts with the printer software to interpret the datastream and render a pagemap. The software interprets the objects, page addresses and print attributes in the datastream, generates bit maps of the objects, and merges the bitmaps into the pagemap at the appropriate page address. The application program arranges the objects in the datastream in the order in which they were created by the application program, thus enabling the datastream to be rendered sequentially while maintaining the proper relative relationship of the objects on the page. However, in systems of this type, in which the entire page is rendered before any part of the page is dispatched to the print engine, a large amount of memory is required to accommodate the entire pagemap. In addition, the processing time to generate a number of pages can be very high, since an entire page must be rendered prior to dispatch, and the system must wait for the dispatch operation to be completed before beginning to render the next page. Thus, while this system is beneficial in terms of maintaining the correct placement and relationship of the objects on the page, it is not practical in a high-speed printing system due to its high processing time.
Other systems have been developed which break the pagemap into geographical regions or "bands," and separately rasterize and dispatch each band. This banding scheme allows rectangular sections of the pagemap to be rasterized and dispatched to the print engine without rasterizing the entire pagemap. In the past, this technology was applied in situations where memory conservation was a critical factor or in situations where the printer hardware did not use a PDL and required a host computer system to interpret the PDL and deliver the image in sections. In these systems, banding was a means to circumvent the limitations of the printing hardware or software. Each band is a fixed rectangle encompassing a set number of rows and columns of bits in the pagemap, the number of rows and columns being tailored to the printer hardware. These systems do not require as much memory, since they need only enough memory to hold a band rather than an entire pagemap. These systems appear to enable the rendering and dispatching of bands to be carried out in parallel, thereby reducing the overall processing time. However, these systems have drawbacks which severely limit any performance benefits. Since the objects may be presented in any order, the rendering software may not allow the first band to be dispatched until the last object is examined. This is due to the possibility that the last object may affect the first band.
To address the lack of performance in these systems, a type of banding is employed which allows the rendering and dispatching operations to proceed in an interleaved manner. This achieves an increase in performance by allowing the print engine to imprint a section of the desired page while the next section is being generated. Like the previous solution, objects are created by interpreting the PDL data stream, but, before rasterizing, the software is made to sort and duplicate those objects. Sorting the objects by page address into the correct geographical order before rendering assures that, when mapped, each band includes all of the objects associated with the corresponding area of the page. In addition, since the objects are sorted, the software can detect when each band is finished and dispatch it while rendering the next band. Presorting consumes a large amount of processing time considerably slowing the printing speed. As the processor evaluates each object for the purpose of sorting, it must examine the rendering commands for each object, to determine the extent the object occupies the page and to determine the affected bands. Again, rectangular bands are used as it simplifies the geometry used in determining which bands are affected. Any object which affects multiple bands is duplicated for each band affected and the copies reserved for rendering subsequent bands. This subjects each object to a thorough geometric analysis to determine its extent and the manner in which it affects subsequent bands, thus consuming more processing time. Since the last object may affect the first band, the interpretation of the PDL data stream (object creation) must still be completed before the rendering and dispatch operations. At this point the software may begin rasterizing object into bands. The processor needs to examine each object a second time in order to limit the rasterization of large objects to the current band.
While the latter system provides some performance by interleaving the rasterizing of objects and dispatch of bands, it does not eliminate the need to presort the page objects in order to assure that all of the objects are mapped into the correct bands. Now the software must evaluate the rendering commands, sort them into precise order, analyze and duplicate them for subsequent bands before initiating the final stages where performance has been increased. Therefore, these systems still involve a processing bottleneck in interpreting, rendering and dispatching the page.
Thus, it is desirable to have a system for interpreting, rendering and rasterizing an image which substantially increases the effective speed of the raster image processor, in order to meet the growing need for faster and more efficient printing systems.